package com.zl.driversmaxincome;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

// 暴力递归->动态规划
public class DriversMaxIncome {
    /**
     *
     * @param income 第一维司机编号. 第二维去A，B区域的收入
     */
    public int driversMaxIncome(int[][] income) {
        int N = income.length >> 1;
        return f(income,0,N,N);
    }

    /**
     * 暴力递归
     * @param income 第一维司机编号. 第二维去A，B区域的收入
     * @param d 从d号开始往后的所有司机
     * @param pA A区所剩名额
     * @param pB B区所剩名额
     * @return 从d开始往后司机最大收入分配方案
     */
    public int f(int[][] income, int d, int pA,int pB) {
        // 没有后续司机需要分配
        if (d == income.length) {
            // 所以收入为0
            return 0;
        }
        // A区名额用完
        if (pA == 0) {
            // 所以当前d位置的司机只能分配到B区,B区收入+后续司机分配的最大收入
            return income[d][1] + f(income,d+1,pA,pB-1);
        }
        // B区名额用完
        if (pB == 0) {
            // 所以当前d位置的司机只能分配到A区,A区收入+后续司机分配的最大收入
            return income[d][0] + f(income,d+1,pA-1,pB);
        }
        // 名额都没用完,就有两种尝试方案
        // d位置司机去B区,B区收入+后续司机分配的最大收入
        int p1 = income[d][1] + f(income,d+1,pA,pB-1);
        // d位置司机去A区,A区收入+后续司机分配的最大收入
        int p2 = income[d][0] + f(income,d+1,pA-1,pB);
        // 取两种尝试的最大值
        return Math.max(p1,p2);
    }

    public int driversMaxIncome1(int[][] income) {
        int N = income.length >> 1;
        return f1(income,0,N);
    }

    /**
     * 小优化
     * @param income 第一维司机编号. 第二维去A，B区域的收入
     * @param d 从d号开始往后的所有司机
     * @param pA A区所剩名额
     * @return 从d开始往后司机最大收入分配方案
     */
    public int f1(int[][] income,int d,int pA) {
        if (d == income.length) {
            return 0;
        }
        if (pA == 0) {
            return income[d][1] + f1(income,d+1,pA);
        }
        if (income.length - d == pA) {
            return income[d][0] + f1(income,d+1,pA-1);
        }
        int p1 = income[d][1] + f1(income,d+1,pA);
        int p2 = income[d][0] + f1(income,d+1,pA-1);
        return Math.max(p1,p2);
    }

    /**
     * 动态规划 三维dp表
     * @param income 司机收入矩阵
     * @return 返回整体最大分配收入
     */
    public int dp(int[][] income) {
        int N = income.length;
        int M = N >> 1;
        int[][][] dpT = new int[N+1][M+1][M+1];
        for (int d = N-1; d >= 0; d--) {
            for (int a = 0; a <= M; a++) {
                for (int b = 0; b <= M; b++) {
                    if (a == 0) {
                        if (b > 0) {
                            dpT[d][a][b] = income[d][1] + dpT[d + 1][a][b - 1];
                        }
                    } else if (b == 0) {
                        dpT[d][a][b] = income[d][0] + dpT[d + 1][a - 1][b];

                    } else {
                        int p1 = income[d][1] + dpT[d + 1][a][b - 1];
                        int p2 = income[d][0] + dpT[d + 1][a - 1][b];
                        dpT[d][a][b] = Math.max(p1,p2);
                    }
                }
            }

        }
        return dpT[0][M][M];
    }

    /**
     * 动态规划 二维dp表
     * @param income 司机收入矩阵
     * @return 返回整体最大分配收入
     */
    public int dp1(int[][] income) {
        int N = income.length;
        int M = N >> 1;
        int[][] dpT = new int[N+1][M+1];
        for (int d = N-1; d >= 0; d--) {
            for (int a = 0; a <= M; a++) {
                if (a == 0) {
                    dpT[d][a] = income[d][1] + dpT[d+1][a];
                } else if (N - d == a) {
                    dpT[d][a] = income[d][0] + dpT[d+1][a-1];
                } else {
                    dpT[d][a] = Math.max(income[d][1] + dpT[d+1][a],income[d][0] + dpT[d+1][a-1]);
                }
            }
        }
        return dpT[0][M];
    }
}
